package com.gitee.feizns.explore.data_structure.queue.island;

/**
 * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
 * 一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 * 你可以假设网格的四个边均被水包围。
 * @author feizns
 * @since 2019/11/15
 */
public class IsLand {

    public static void main(String[] args) {
        System.out.println(numIslands(new char[][]{
                {'1', '1', '1', '0'},
                {'1', '1', '1', '0'},
                {'0', '0', '0', '1'},
                {'1', '1', '1', '1'}
        }));
    }

    public static int numIslands(char[][] grid) {
        int ret = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if ( grid[i][j] == '1' ) {
                    ret++;
                    setZero(grid, i, j);
                }
            }
        }
        return ret;
    }

    private static void setZero(char[][] grid, int x, int y) {
        if ( grid.length > 0 ) {
            int w = grid.length;
            int h = grid[0].length;
            if ( x >= 0 && x < w && y >= 0 && y < h ) {
                if ( grid[x][y] == '1' ) {
                    grid[x][y] = '0';
                    setZero(grid, x + 1, y);
                    setZero(grid, x - 1, y);
                    setZero(grid, x, y + 1);
                    setZero(grid, x, y - 1);
                }
            }
        }
    }

//    public static int numIslands(char[][] grid) {
//        Set<Point> points = new HashSet<>();
//        int ret = 0;
//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[i].length; j++) {
//                Point curt = new Point(i, j);
//                if ( grid[i][j] == '1' && !points.contains(curt) ) {
//                    ret++;
//                    Queue<Point> queue = new LinkedList<>();
//                    queue.add(curt);
//                    while ( !queue.isEmpty() ) {
//                        Point remove = queue.remove();
//                        List<Point> list = aroundPoints(remove, grid.length, grid[i].length);
//                        for (Point point : list) {
//                            if ( grid[point.x][point.y] == '1' && !points.contains(point) ) {
//                                points.add(point);
//                                queue.add(point);
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        return ret;
//    }
//
//    private static List<Point> aroundPoints(Point point, int w, int h) {
//        Predicate<Point> test = p -> p.x >= 0 && p.x < w && p.y >= 0 && p.y < h;
//        Point top = new Point(point.x + 1, point.y);
//        Point bot = new Point(point.x - 1, point.y);
//        Point lef = new Point(point.x, point.y - 1);
//        Point rig = new Point(point.x, point.y + 1);
//        return new ArrayList<>(Arrays.asList(top, bot, lef, rig)).stream().filter(test).collect(Collectors.toList());
//    }
//
//    private static class Point {
//
//        private int x, y;
//
//        public Point(int x, int y) {
//            this.x = x;
//            this.y = y;
//        }
//
//        @Override
//        public boolean equals(Object o) {
//            if (this == o) return true;
//            if (o == null || getClass() != o.getClass()) return false;
//            Point point = (Point) o;
//            return x == point.x &&
//                    y == point.y;
//        }
//
//        @Override
//        public int hashCode() {
//            return Objects.hash(x, y);
//        }
//    }

}
